// 给定一个二叉树，原地将它展开为一个单链表。

//  

// 例如，给定二叉树

//     1
//    / \
//   2   5
//  / \   \
// 3   4   6
// 将其展开为：

// 1
//  \
//   2
//    \
//     3
//      \
//       4
//        \
//         5
//          \
//           6


// Definition for a binary tree node.
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};

// inplace
class Solution {
public:
    void flatten(TreeNode* root) {
        while (root != nullptr) {
            if (root->left != nullptr) {
                auto most_right = root->left; // 如果左子树不为空, 那么就先找到左子树的最右节点
                while (most_right->right != nullptr) most_right = most_right->right; // 找最右节点
                most_right->right = root->right; // 然后将根的右孩子放到最右节点的右子树上
                root->right = root->left; // 这时候跟的右孩子可以释放, 因此我令左孩子放到右孩子上
                root->left = nullptr; // 将左孩子置为空
            }
            root = root->right; // 继续下一个节点
        }
    }
};

// 递归
class Solution {
public:
    void flatten(TreeNode* root) {
        root = build(root);
    }
    TreeNode* build(TreeNode* node) {
        if (node == nullptr || (node->left == nullptr && node->right == nullptr))
            return node;
        node->left = build(node->left);
        node->right = build(node->right);
        // 找到左子树的最右端
        TreeNode* p = node->left;
        if (p) {
            while (p->right != nullptr) p = p->right;
            p->right = node->right;
            node->right = node->left;
        }
        node->left = nullptr;
        return node;
    }
};

 /* 寻找前驱结点
当前节点的左子树不为空，则找出左子树的最右节点
 */
class Solution {
public:
    void flatten(TreeNode* root) {
        TreeNode* cur = root;
        while (cur != nullptr) {
            if (cur->left != nullptr) {
                TreeNode* pre = cur->left; // 当前右子树的前驱节点
                while (pre->right != nullptr) {
                    pre = pre->right;
                }
                pre->right = cur->right; // 将当前右子树变为前驱结点的右子树
                cur->right = cur->left; // 将当前左子树变为右子树
                cur->left = nullptr;
            }
            cur = cur->right;
        }
    }
};